// scaup - Scala up!
// (c) 2008-2009, Normen Müller, normen.mueller@gmail.com  
// $Id: E.scala 39 2009-11-10 18:58:30Z normen.mueller $
package scaup.eq

/** 
 * @author <a href="mailto:normen.mueller@googlemail.com">Normen M&#xFC;ller</a>
 * @version 0.0.2 */
case class Slit[T](val before: Option[Seq[T]],val focus: Option[T],val after: Seq[T])
  
/** An equivalence system.
 * 
 *  An equivalence system is a set of equivalence relations.
 * 
 *  Q: Why contravariant type constructor?
 *  A: If S <: T then E[T] <: E[S] wrt. the cardinality of equal elements.  For example, XML <: AnyRef but
 *     within the equivalence model model of XML more elements are considers to be equal than within
 *     the equivalence model model of AnyRef
 *
 * @author <a href="mailto:normen.mueller@googlemail.com">Normen M&#xFC;ller</a>
 * @version 0.0.2 */
trait EquivalenceSystem[-T] {  
  def findEquivTo[S <: T](ctx: Seq[S],elem: S): Slit[S] = findEquivTo(ctx,elem,Nil)
  
  private def findEquivTo[S <: T](ctx: Seq[S],elem: S,acc: Seq[S]): Slit[S] = ctx match {
    case Nil | Seq.empty         => Slit(None,None,acc)
    case _ if equiv(elem,ctx(0)) =>
      if(ordered(elem)) acc match {
        case Nil | Seq.empty => Slit(None,Some(ctx(0)),ctx.drop(1))
        case _               => Slit(Some(acc),Some(ctx(0)),ctx.drop(1))
      } else Slit(None,Some(ctx(0)),acc ++ ctx.drop(1))
    case _                       => findEquivTo(ctx.drop(1),elem,acc ++ Seq(ctx(0)))
  }
  
  def equiv[S <: T](l: S,r: S): Boolean = l == r
  
  def equiv[S <: T](ls: Seq[S],rs: Seq[S]): Boolean = ls.length == rs.length && (ls forall (e => rs exists (equiv(e,_))))
  
  def ordered[S <: T](l: S): Boolean = true
}

